package leetcode.D400.T301;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    private int maxBorder = 0;
    private int maxLen = -1;

    /**
     * 遇到(则score+1，遇到)则score-1。结果的score必然为0。采用dfs+剪枝算法
     */
    public List<String> removeInvalidParentheses(String s) {
        int leftNum = 0, rightNum = 0;
        for (int i = 0; i<s.length(); ++i) {
            if (s.charAt(i) == '(')
                leftNum++;
            else if (s.charAt(i) == ')')
                rightNum++;
        }
        maxBorder = Math.min(leftNum, rightNum);
        Set<String> set = new HashSet<>();
        dfs(s, 0, set, 0, new StringBuilder());
        return new ArrayList<>(set);
    }

    /**
     * res和maxLen用于记录结果，res使用Set结构用于去重
     * 每当走到cur时，都有两个选择，要么选要么不选
     * score必须在[0, maxBorder]之间，否则直接不选
     * 如果不是(或），那么直接选
     */
    private void dfs(String s, int cur, Set<String> res, int score, StringBuilder sb) {
        if (cur == s.length()) {
            if (score != 0)
                return;
            if (sb.length() > maxLen) {
                maxLen = sb.length();
                res.clear();
                res.add(sb.length() == 0 ? "" : sb.toString());
            } else if (sb.length() == maxLen) {
                res.add(sb.toString());
            }
            return;
        }
        char c = s.charAt(cur);
        if ((c == '(' && score+1>maxBorder) || (c == ')' && score-1<0)) {
            dfs(s, cur + 1, res, score, sb);
            return;
        }
        if (c == '(' || c == ')') {
            dfs(s, cur + 1, res, score, sb);
        }
        sb.append(c);
        dfs(s, cur + 1, res, score + ((c == '(') ? 1 : ((c == ')') ? -1 : 0)), sb);
        sb.deleteCharAt(sb.length()-1);
    }
}